Bitmap 位图排序
Bitmap 的原理和应用
使用 bitmap 主要是可以减少存储空间的使用，用一个 bit 来存储一个元素的状态。当我们需要在一亿个数中判断某个数是否存在时，我们不需要将这一亿个数同时放入内存。
一个 bit 有 2 种状态，0 或者 1
所以 1 个 byte 可以表示 0000 0000 -> 1111 1111，也就是十进制的 0 到 255
其中十进制和二进制对应关系如下：
0 ---------> 0000 0000
1 ---------> 0000 0001
2 ---------> 0000 0010
3 ---------> 0000 0011
4 ---------> 0000 0100
5 ---------> 0000 0101
6 ---------> 0000 0110
7 ---------> 0000 0111
8 ---------> 0000 1000
9 ---------> 0000 1001
10 ---------> 0000 1010
11 ---------> 0000 1011
12 ---------> 0000 1100
13 ---------> 0000 1101
14 ---------> 0000 1110
15 ---------> 0000 1111
.......................
.......................
255...........1111 1111
在大部分编程语言里面，int 类型一般的都是占 4 个 byte，也是 32 位，甭管你这个数字是 1 或者是 21亿你都得占 32 位，所以如果你现在有 10 亿数字需要存放在内存里面，需要多少内存呢？
大概需要 3800MB 内存，这里计算出的数值只适合 C，在 PHP 里面，一个整型变量占用的实际空间远远大于 4byte，是好几倍！
为了解决这个问题，bitmap 采用了一种映射机制，举个例子，假如有 1, 3, 7, 2, 5 这 5 个数字需要存放，正常情况下你需要 ,但 bitmap 只需要 1byte，它是咋做到呢？
假设下面是 1byte，首先将所有位置为 0：
0 0 0 0 0 0 0
从第一个 0 开始数数，把对应数字的位置置为 1，比如说第一个 1 那就是第 2 个位置置为 1，第二个 3 就是把第 4 个位置置为 1，依此论推...
1 => 0 1 0 0 0 0 0 0
3 => 0 0 0 1 0 0 0 0
7 => 0 0 0 0 0 0 0 1
2 => 0 0 1 0 0 0 0 0
5 => 0 0 0 0 0 1 0 0
叠加起来最终的串就是：
0 1 1 1 0 1 0 1
其实最终的数字和二进制没有什么关系，纯粹是数数，这个串就可以代表最大到 7 的数字，然后我们就开始数数，从 0 开始：
比如第 1 个位置是 1，那就记个 1
比如第 2 个位置是 1，那就记个 2
比如第 3 个位置是 1，那就记个 3
比如第 5 个位置是 1，那就记个 5
比如第 7 个位置是 1，那就记个 7
结果就是 1 2 3 5 7，不仅仅排序了，而且还去重了！如果按照这种转换机制，1 个 int 类型，32 位的话，可以表示 0-31 之间的数字！
如果要表示最大 1万的数，那就需要 1万个位的串，但是编程语言并没有这样的数据类型，但是可以用数组去模拟
举个例子：一个整型是 32位，也就说我们大概需要 314个数组元素来表示这个串
数组第 1 个元素 00 - 31
数组第 2 个元素 32 - 63
数组第 3 个元素 64 - 95
数组第 4 个元素 96 - 127
... ...
Int 的大小
一个 Int 等于 4 个 Byte 等于 4 * 8 个 Bit
判断某个数的第 i 位是0 还是 1？
思路：
- 如果第 i 位 与 1 相与 结果为 1 表明第 i 位为 1；
- 如果为 0 表明第 i 位为 0
//获取 整数 num 的第 i 位的值
private static boolean getBit(int num, int i)
{
return ((num & (1 << i)) != 0); //true 表示第i位为1,否则为0
}
1 左移 i 位后，得到一个数，这个数只有第 i 位为 1，其它位都为 0
所以可以引申出，令第 n 位为 1 的操作
// 令 value 的第 index 位为 1
value |= 1 << index;
Bloom Filter（布隆过滤器）
提到这个算法的好处，最大的好处就是节省内存，节省了好几十倍，适合处理大量数据，除了快速排序，还可以做快速去重，快速查询是否存在，还有一个比较好听的应用 Bloom Filter（布隆过滤器）:
Bloom Filter 使用 k 个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到 {1,…,m} 的范围中。对任意一个元素 x，第 i 个哈希函数映射的位置 hi(x) 就会被置为 1（1≤i≤k）。
注：如果一个位置多次被置为 1，那么只有第一次会起作用，后面几次将没有任何效果。 Bloom Filter 在判断 y 是否属于这个集合时，对 y 应用 k 次哈希函数，若所有 hi(y) 的位置都是 1（1≤i≤k），就认为 y 是集合中的元素，否则就认为 y 不是集合中的元素。
补充：位运算符
在 Java 中，int 数据底层以补码形式存储。int 型变量使用 32bit 存储数据，其中最高位是符号位，0 表示正数，1 表示负数，可通过 Integer.toBinaryString() 转换为 bit 字符串，
// 若最高的几位为 0 则不输出这几位，从为 1 的那一位开始输出
System.out.println(Integer.toBinaryString(10));
System.out.println(Integer.toBinaryString(-10));
// 以上会输出（手工排版过，以下的输出均会被手工排版）：
1010
11111111111111111111111111110110
左移 << 符号的使用
例如：5 << 2 = 20
首先会将 5 转为 2 进制表示形式: 0000 0000 0000 0000 0000 0000 0000 0101
然后左移 2 位后，低位补 0： 0000 0000 0000 0000 0000 0000 0001 0100
换算成 10 进制为 20
右移 >> 运算符
例如：5 >> 2 = 1
还是先将 5 转为 2 进制表示形式： 0000 0000 0000 0000 0000 0000 0000 0101
然后右移 2 位，高位补 0： 0000 0000 0000 0000 0000 0000 0000 0001
换算成十进制后是 1
无符号右移 >>> 运算符
例如：5 >>> 3
我们知道在 Java 中 int 类型占 32 位，可以表示一个正数，也可以表示一个负数。正数换算成二进制后的最高位为 0，负数的二进制最高为为 1。
对于 2 进制补码的加法运算，和平常的计算一样，而且符号位也参与运算，不过最后只保留 32位
-5 换算成二进制： 1111 1111 1111 1111 1111 1111 1111 1011
-5 右移3位： 1111 1111 1111 1111 1111 1111 1111 1111 // (用1进行补位，结果为-1)
-5 无符号右移3位: 0001 1111 1111 1111 1111 1111 1111 1111 // (用0进行补位,结果536870911 )
排序
首先有一个 bit 数组，如果我们排序的所有元素中最大的数是一亿，那么我们就需要这个数组大小初始化为一亿零一（加上 0），从 0 排到一亿，每一位 bit 就对应这个数
比如第 6 个 bit 位对应数字 5 的状态，如果是 1 表示待排序中存在 5，是 0，则表示待排序数组中没有 5。
当我们使用待排序数组完成对 bitmap 的填充之后，只需要按位输出存在的数就可以了。
如果待排序中有重复的数字，就会只输出一个。不过也因为 bitmap 的这个特点——重复的数字只出现一次，我们可以使用同样的代码对一堆数字进行去重操作。
public class BitmapSort {
private final int[] bitmap;
public BitmapSort(int maxNumber) {
bitmap = new int[(maxNumber >> 5) + 1];
}
public void sort(int[] array) {
for (int i = 0; i < array.length; i++) {
int num = array[i];
// 这里 >> 5 是什么？ 因为 2 的 5 次方是 32
int bit = num >> 5;
int index = num & ((1 << 5) - 1);
// 令 itmap[bit] 的第 index 位为 1
bitmap[bit] |= 1 << index;
}
for (int i = 0; i < bitmap.length; i++) {
for (int j = 0; j < 32; j++) {
//
if ((bitmap[i] & (1 << j)) != 0) {
System.out.print(i * 32 + j + " ");
}
}
}
}
public static void main(String[] args) {
BitmapSort bitmapSort = new BitmapSort(88);
int[] array = {88,86,45,65,78,75,12,35,24,5,1,23};
bitmapSort.sort(array);
}
}
判断一个数是否存在
一个文件里有一亿个数，我们如何判断 88 是否存在其中？简单就是遍历一遍，但是如果内存不够呢？如果数是 int 型，占 4 个 byte，一亿个数就是 400M，如果十亿个数呢？4个G。
把四个G的数都放入内存，才能完成这个遍历。如果内存不够呢？我们就可以采用 bitmap，记录十亿个数的状态，我们只需要十亿个bit，也就是125M。
先编写一个生成数据的类：
public class Date {
public static boolean makeNumbers(int size){
boolean flag = true;
Random random = new Random();
try {
BufferedWriter bw = new BufferedWriter(new FileWriter("numbers.txt"));
for (int i = 0;i<size;i++){
bw.write(String.valueOf(Math.abs(random.nextInt(size))));
bw.newLine();
}
bw.close();
} catch (IOException e) {
flag = false;
e.printStackTrace();
}
return flag;
}
}
再去查询这个数据
public class IsNumberExist {
private int[] bitmap;
private int size;
private int SHIFT = 5; // 2 的 5 次方是 32
public boolean isNumberExist(int number){
int bit = number>>SHIFT;
int index = number&((1<<SHIFT)-1);
return ((1<<index)&bitmap[bit])!=0;
}
public IsNumberExist(int size){
this.size = size;
bitmap = new int[(size>>SHIFT)+1];
}
public void insertDate(int number){
int bit = number>>SHIFT;
int index = number&((1<<SHIFT)-1);
bitmap[bit] = bitmap[bit]|(1<<index);
}
public void insertFromTxt(String filename){
try {
BufferedReader br = new BufferedReader(new FileReader(filename));
String str = null;
while ((str = br.readLine())!=null){
insertDate(Integer.valueOf(str));
}
br.close();
} catch (IOException e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
Runtime rt = Runtime.getRuntime();
System.out.println("当前JVM所占内存："+(rt.totalMemory() - rt.freeMemory())/1024/1024+"M");
IsNumberExist tool = new IsNumberExist(1000000000);
System.out.println("当前JVM所占内存："+(rt.totalMemory()-rt.freeMemory())/1024/1024+"M");
//Date.makeNumbers(100000000);//生成一亿个数到number.txt
tool.insertFromTxt("numbers.txt");//使用这个一亿个数初始化bitmap的状态
System.out.println(tool.isNumberExist(88888888));//判断88888888是否在这个文件中
System.out.println(tool.isNumberExist(99999999));//判断99999999是否在这个文件中
System.out.println(tool.isNumberExist(91725151));//判断91725151是否在这个文件中
}
}